package Redis.skiplist;

/**
 * @author welsir
 * @version 1.0
 * @description: TODO
 * @date 2022/10/9 10:17
 */
public class SkipList {

    private static final int MAX_LEVEL = 32;    // 结点的个数
    private static final float ZSKIPLIST_P = 0.25f;
    private int levelCount = 1;   // 索引的层级数
    private Node head = new Node();    // 头结点

    public class Node {
        int data = Integer.MIN_VALUE;
        private Node next[] = new Node[MAX_LEVEL];
        private int level = 0;

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", level=" + level +
                    ", nextData="  +
                    '}';
        }
    }

    private int randomLevel() {
        int level = 1;
        while (Math.random() < ZSKIPLIST_P && level < MAX_LEVEL)
            level++;
        return level;
    }

    public void insert(int val) {
        int level = randomLevel();
        Node curnode = new Node();
        curnode.data = val;
        curnode.level = level;
        System.out.println("输入"+val);
//      建立与此节点层级一样的数组，查找每个层级对应的节点数据
        Node update[] = new Node[level];
        for (int i = 0; i < level; i++) {
            update[i] = head;
        }
        Node tmp = head;

//        找同层级的节点，并赋值给update
        for (int i = level - 1; i >= 0; --i) {
//            向右查找到小于val值的节点
            while (tmp.next[i] != null && tmp.next[i].data < val) {
                System.out.println("tmpData为:"+tmp.data);
                tmp = tmp.next[i];
            }
            update[i] = tmp;
        }

//        使当前节点的每个层级与update关联起来
        for (int i = 0; i < level; i++) {
            curnode.next[i] = update[i].next[i];
            update[i].next[i] = curnode;
        }
//        更新层级
        if (level > levelCount)
            levelCount = level;
    }

    public void delete(int val){
        Node[] update = new Node[levelCount];

//        找出该每层要删除的索引位置
        Node tmp = head;
        for(int i=levelCount-1;i>=0;i--){
            while (tmp.next[i]!=null&&tmp.next[i].data<val){
                tmp = tmp.next[i];
            }
            update[i] = tmp;
        }

//        保证底层节点不为空且下一节点对应的值为待删除值
        if(tmp.next[0]!=null&&tmp.next[0].data==val){
            for(int i= levelCount-1;i>=0;i--){
                if(update[i].next[i]!=null&&update[i].next[i].data==val){
                    update[i].next[i] = update[i].next[i].next[i];
                }
            }
        }

//        减少层级，如果需要
        while (levelCount>1&&head.next[levelCount]==null){
            levelCount--;
        }
    }

//    查找
    public Node find(int val){
        Node tmp = head;

        for(int i=levelCount-1;i>=0;i--){
//            找出当前节点的前一个节点
            while (tmp.next[i]!=null&&tmp.next[i].data<val){
                tmp = tmp.next[i];
            }
        }
//             如果满足条件，说明找到了
        if(tmp.next[0]!=null&&tmp.next[0].data==val)
            return tmp.next[0];
        else
            return null;
    }
    public void printNode() {
        Node tmp = head;
        while (tmp.next[0] != null) {
            System.out.println(tmp.next[0]);
            tmp = tmp.next[0];
        }
    }
}
